1. Field of the Invention
The present invention relates to compilers, and more particularly to list schedulers used in association with compilers.
2. Description of the Related Art
When computer program source code is compiled, the result is a list of machine instructions capable of execution by a target processor. The program which converts source code to machine instructions is referred to as a compiler.
Most compilers incorporate a list scheduler. A list scheduler orders machine instructions in an attempt to improve the efficiency of their execution. The efficiency of a particular ordering of machine instructions is typically measured by the amount of time required for a target processor to execute the machine instructions. The list scheduler typically reorders an interim ordering of instructions that is generated during a first pass of the compilation process.
The behaviour of a list scheduler is governed by one or more heuristics. A heuristic is a particular method of ordering machine instructions. An example of a commonly used heuristic is the Critical Path Heuristic. Heuristics may be applied by a list scheduler individually or in combination.
When a set of machine instructions which has been ordered using known heuristics is executed, the registers of the target processor can become overcommitted. A processor's registers are said to become overcommitted when a machine instruction calls for the use of a register, but all of the processor's registers are already in use. In this situation, “spill code” is typically generated which causes one or more registers to be vacated, so that program execution may proceed. Vacating a register typically entails storage of its contents to volatile memory and, after the register has been used for the execution of a machine instruction, restoration of its previous contents from volatile memory. Spill code tends to degrade efficiency, as each volatile memory access can waste a significant number of clock cycles. This is especially true in respect of modern processors whose speeds may be significantly faster than the speeds associated with volatile memory.
Accordingly, a need exists for a heuristic which addresses the above noted difficulty in the prior art.